home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Cream of the Crop 1
/
Cream of the Crop 1.iso
/
PROGRAM
/
NTUMIN10.ARJ
/
LOGMIN_A.C
< prev
next >
Wrap
C/C++ Source or Header
|
1992-03-12
|
17KB
|
512 lines
/****************************************************************************
*
* Program name : LOGMIN_A.C
*
* Written By : Eng-Huat Ong and Kian-Mong Low.
*
* This is where the original LOGMIN algorithmn is implemented.
*
* --------------------------------------------------------------------------
* Copyright (c) 1992. All Rights Reserved. Nanyang Technological
* University.
*
* You are free to use, copy and distribute this software and its
* documentation providing that:
*
* NO FEE IS CHARGED FOR USE, COPYING OR DISTRIBUTION.
*
* IT IS NOT MODIFIED IN ANY WAY.
*
* THE COPYRIGHT NOTICE APPEAR IN ALL COPIES.
*
* This program is provided "AS IS" without any warranty, expressed or
* implied, including but not limited to fitness for any particular
* purpose.
*
* If you find NTUMIN fast, easy, and useful, a note or comment would be
* appreciated. Please send to:
*
* Boon-Tiong Tan or Othman Bin Ahmad
* School of EEE
* Nanyang Technological University
* Nanyang Avenue
* Singapore 2263
* Republic of Singapore
*
***************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define mask8 255
unsigned char *logmin_a(a, b) /* pointer to a & b array passed */
unsigned char *a, *b;
{
unsigned short pterm, ma, mb, pos;
unsigned short *ca, *mp, m_cnt;
unsigned long m, j, size, addr, count, count1, topow();
register long i, wo, wi;
char test;
unsigned char *c, *d, *e, *s, *temp, *cp, *mt, *at, *ad;
unsigned char n, adj, adj0, adji, adjacency(), nspm, cover;
unsigned char *adjacent(), *reduce(), *cpt(), *ssm(), adj_of_mi();
mb = *(b+2)<<8 | *(b+1); /* no. of minterms in b-array */
n = *a; /* no. of variables */
nspm = *(a+3); /* no. of bytes/minterm */
ma = *(a+2)<<8 | *(a+1); /* no. of minterms in a-array */
temp = (unsigned char *) malloc(nspm+1); /* temporary storage */
if (temp == 0)
{
printf("Out of memory -- LOGMIN_A, *temp\n");
printf("Program terminated - 1\n");
exit(0);
}
s = (unsigned char *) malloc(4); /* header of s-array */
if (s == 0)
{
printf("Out of memory -- LOGMIN_A, *s\n");
printf("Program terminated - 2\n");
exit(0);
}
/***********\
* PHASE I *
\***********/
pterm = 0; /* no. of product term */
count = 0; /* no. of terms stored for phase II */
/***
*** DETERMINE ADJACENCY OF ALL MINTERMS AND GENERATE THEIR CPT
***/
for (i=0; i<mb; i++) /* for all minterms in b-array */
{
*b = n; /* assign back to n */
memcpy(temp, (b+4+nspm*i), nspm); /* pick a minterm from b-array */
c = adjacent(temp, a, 255); /* obtain the adjacent terms */
adj = *(c+1); /* adjacency of minterm */
d = cpt(c); /* generate CPT */
/***
*** MINIMIZE ALL MINTERMS WITH ADJACENCY OF 0 & 1 FIRST
***/
if (adj <= 1) /* adjacency 0 or 1 */
{
s = (unsigned char *) realloc(s,4+n*(pterm+1)); /* more space */
if (s == 0)
{
printf("Out of memory -- LOGMIN_A, *s\n");
printf("Program terminated - 3\n");
exit(0);
}
memcpy ((s+4+n*pterm),d,n); /* add CPT to soln array */
pterm++; /* product term count */
b = reduce(c,b,i); /* remove minterms covered from b-array */
i = (char) *b; /* index pointer of b-array */
mb = *(b+2)<<8 | *(b+1); /* value of mb altered in b-array */
}
else /* adj > 1 */
{
/***
*** MINTERMS WITH ADJACENCY GREATER THAN 1, GENERATE SSM AND TEST FOR COVERAGE
***/
e = ssm(d); /* generate SSM */
m = topow(*(e+1)); /* no. of SSM terms */
for (j=0; j<m; j++) /* check for SSM coverage */
{
memcpy (temp, (e+4+nspm*j), nspm); /* pick SSM term */
test = exist (temp, a, ma);
if (test == -1) /* minterm not in a-array */
break;
}
/***
*** ALL SSM COVERED BY THE FUNCTION, SELECT CPT AS PRODUCT TERM
***/
if (test == 0) /* all SSM's covered by fn */
{
if (m > 65536) /* too many SSM terms */
{
printf("Product Term Too Huge \n");
printf("Program terminated \n");
exit(0);
}
*e = n; /* no. of variables */
*(e+1) = (m-1) & mask8; /* no. of SSM terms minus 1 */
*(e+2) = (m-1)>>8 & mask8;
b = reduce(e,b,i); /* remove minterms covered from b-array */
i = (char) *b; /* index pointer of b-array */
mb = *(b+2)<<8 | *(b+1); /* no. of minterms in b-array */
s = (unsigned char *) realloc(s, 4+n*(pterm+1)); /* more space */
if (s == 0)
{
printf("Out of memory -- LOGMIN_A, *s\n");
printf("Program terminated - 4\n");
exit(0);
}
memcpy((s+4+n*pterm),d,n); /* add CPT to soln array */
pterm++; /* no. of product terms */
}
else
{
/***
*** NOT COVERED, STORE UNCOVERED MINTERMS, ITS CORRESPONDING
*** ADJACENCY, ADJACENT TERMS AND CPT FOR PHASE II
***/
count++; /* no. of terms for phase II */
if (count==1) /* 1st uncovered term */
{
ad = (unsigned char *) malloc(1); /* array of adjacency */
if (ad==0)
{
printf("Out of memory -- LOGMIN_A, *ad\n");
printf("Program terminated - 5\n");
exit(0);
}
cp = (unsigned char *) malloc(n); /* array of CPT's */
if (cp==0)
{
printf("Out of memory -- LOGMIN_A, *cp\n");
printf("Program terminated - 6\n");
exit(0);
}
mt = (unsigned char *) malloc(4+nspm*count); /* array of minterms */
if (mt==0)
{
printf("Out of memory -- LOGMIN_A, *mt\n");
printf("Program terminated - 7\n");
exit(0);
}
size = 4 + nspm*(1+adj); /* addr counter of at-array */
at = (unsigned char *) malloc (4+nspm*(1+adj)); /* all adj terms from c-arrays */
if (at==0)
{
printf("Out of memory -- LOGMIN_A, *at\n");
printf("Program terminated - 8\n");
exit(0);
}
ca = (unsigned short *) malloc(2); /* array of addr of at-array */
if (ca==0)
{
printf("Out of memory -- LOGMIN_A, *ca\n");
printf("Program terminated - 9\n");
exit(0);
}
addr = 0; /* starting address of at-array */
}
else /* subsequent uncovered terms */
{
ad = (unsigned char *) realloc(ad, count); /* adjacency */
if (ad==0)
{
printf("Out of memory -- LOGMIN_A, *ad\n");
printf("Program terminated - 10\n");
exit(0);
}
cp = (unsigned char *) realloc(cp,n*count); /* CPT's */
if (cp==0)
{
printf("Out of memory -- LOGMIN_A, *cp\n");
printf("Program terminated - 11\n");
printf("n = %d, count = %d\n", n, count);
exit(0);
}
mt = (unsigned char *) realloc(mt,4+nspm*count); /* minterms */
if (mt==0)
{
printf("Out of memory -- LOGMIN_A, *mt\n");
printf("Program terminated - 12\n");
exit(0);
}
size+=4+nspm*(1+adj); /* addr counter of at-array */
at = (unsigned char *) realloc (at,size); /* all adj terms from c-arrays */
if (mt==0)
{
printf("Out of memory -- LOGMIN_A, *mt\n");
printf("Program terminated - 13\n");
exit(0);
}
ca = (unsigned short *) realloc(ca,2*count); /* addr of at-array */
if (ca==0)
{
printf("Out of memory -- LOGMIN_A, *ca\n");
printf("Program terminated - 14\n");
exit(0);
}
}
/***
*** STORE IN ARRAYS FOR PHASE II
***/
*(ad+(count-1)) = adj; /* adjacency */
memcpy((cp+n*(count-1)),d,n); /* CPT's */
memcpy((mt+4+nspm*(count-1)),(b+4+nspm*i),nspm); /* minterms */
memcpy((at+addr),c,4+nspm*(1+adj)); /* adj terms */
*(ca+(count-1)) = addr; /* addr of at-array */
addr = size; /* update addr */
}
free(e); /* free pointer */
}
free(c); /* free pointers */
free(d);
}
count1 = count; /* no. of terms for phase II */
/************\
* PHASE II *
\************/
while (count > 0) /* some terms stored for phase II */
{
/***
*** SELECT NEXT MINTERM WITH THE LOWEST ADJACENCY AND AT LEAST ONE OF
*** ITS ADJACENT TERMS PREVIOUSLY COVERED
***/
adj0 = 255; /* set to max of 8-bit */
for (i=0; i<count1; i++) /* do for all adj terms in phase II */
{
if (*(ad+i)<adj0 && *(ad+i)!=0) /* choose minterms with lowest adj */
{
if (adj0 != 255) /* not the first lowest */
free(mp);
adj0 = *(ad+i); /* new lowest value */
m_cnt = 1; /* reset count to 1 */
mp = (unsigned short *) malloc(2); /* space for pos of lowest adj */
if (mp==0)
{
printf("Out of memory -- LOGMIN_A, *mp\n");
printf("Program terminated - 15\n");
exit(0);
}
*mp = i; /* first element */
}
else if (*(ad+i) == adj0) /* adj as large */
{
m_cnt++; /* no. of element in mp-array */
mp = (unsigned short *) realloc(mp, 2*m_cnt); /* more space */
if (mp==0)
{
printf("Out of memory -- LOGMIN_A, *mp\n");
printf("Program terminated - 16\n");
exit(0);
}
*(mp+m_cnt-1) = i; /* elements in mp-array */
}
}
/***
*** SELECT FROM MP-ARRAY, A MINTERM WITH AT LEAST ONE ADJACENT TERM PREVIOSLY
*** COVERED
***/
for (i=0; i<m_cnt; i++) /* do for all in mp-array */
{
adj = *(ad+ *(mp+i)); /* adjacency from ad-array */
c = (unsigned char *) malloc(4+nspm*(1+adj)); /* space for adj terms */
if (c == 0)
{
printf("Out of memory -- LOGMIN_A, *c\n");
printf("Program terminated - 17\n");
exit(0);
}
memcpy(c, (at+ *(ca+ *(mp+i))), 4+nspm*(1+adj)); /* adj terms from at-array */
for (j=0; j<adj; j++) /* check for at least 1 adj term covered */
{
memcpy(temp, (c+4+nspm*(1+j)),nspm);
test = exist(temp,b,mb);
if (test == -1) /* adj term covered */
break;
}
if (test == -1) /* adj term covered */
break;
else
free(c); /* free pointer */
}
if (test == -1) /* adj term covered */
pos = *(mp+i); /* position of minterm required */
else /* none of adj terms covered */
{
adj = *(ad+ *mp); /* choose adj of 1st minterm */
pos = *mp; /* position of 1st minterm */
c = (unsigned char *) malloc(4+nspm*(1+adj)); /* space for adj terms */
if (c == 0)
{
printf("Out of memory -- LOGMIN_A, *c\n");
printf("Program terminated - 18\n");
exit(0);
}
memcpy(c, (at+ *(ca+pos)), 4+nspm*(1+adj)); /* adj terms from at-array */
}
d = (unsigned char *) malloc(n+1); /* space for corresponding CPT */
if (d == 0)
{
printf("Out of memory -- LOGMIN_A, *d\n");
printf("Program terminated - 19\n");
exit(0);
}
memcpy(d, (cp+n*pos), n); /* corresponding CPT from cp-array */
*(d+n) = '\0'; /* terminate with NULL string */
e = ssm(d); /* generate SSM */
free(d); /* free pointers */
free(mp);
/***
*** KEEP SHRINKING THE CPT UNTIL THE SELECTED MINTERM IS COVERED BY THE FUNCTION
***/
cover = 0; /* coverage status */
while (!cover) /* do until shrinked CPT is covered */
{
/***
*** SELECT THE 1ST ADJACENT TERM WITH THE LOWEST WI TO SHRINK AWAY
*** WI IS THE NO. OF TERMS ADJACENT TO THE ADJACENT TERMS THAT ARE
*** SSM, E-ARRAY BUT NOT IN THE FUNCTION, A-ARRAY
***/
wo = -1; /* initial value */
for (i=0; i<adj; i++) /* do for all adjacent terms */
{
memcpy(temp, (c+4+nspm*(i+1)), nspm); /* pick adjacent term */
wi = adj_of_mi(temp,e,a); /* obtain wi */
if (wi>wo)
{
wo = wi; /* new largest value */
pos = i; /* position of adj terms */
}
}
free(e); /* free pointer */
adj--; /* decrement adjacency */
*(c+1) = adj; /* update in c-array */
memcpy((c+4+nspm*(1+pos)), (c+4+nspm*(2+pos)), nspm*(adj-pos)); /* shrink c-array */
c = (unsigned char*) realloc(c, 4+nspm*(1+adj)); /* decrease space */
if (c == 0)
{
printf("Out of memory -- LOGMIN_A, *c\n");
printf("Program terminated - 20\n");
exit(0);
}
d = cpt(c); /* generate CPT */
e = ssm(d); /* generate SSM */
m = topow(*(e+1)); /* no. of SSM terms */
for (i=0; i<m; i++) /* check SSM coverage by function */
{
memcpy(temp, (e+4+nspm*i), nspm); /* pick SSM term */
test = exist(temp,a,ma);
if (test == -1) /* SSM not covered */
break;
}
/***
*** SHRINKED SSM COVERED BY FUNCTION, REDUCE B-ARRAY AND
*** SELECT SHRINKED CPT AS PRODUCT TERM
***/
if (test==0) /* SSM covered */
{
if (m > 65536) /* too many SSM terms */
{
printf("Product Term Too Huge \n");
printf("Program terminated \n");
exit(0);
}
*e = n; /* no. of variables */
*(e+1) = (m-1) & mask8; /* no. of SSM terms minus 1 */
*(e+2) = (m-1)>>8 & mask8;
b = reduce(e, b, m); /* remove minterms covered from b-array */
mb = *(b+2)<<8 | *(b+1); /* no. of minterms in b-array */
count = mb; /* count of no. of minterms not covered */
s = (unsigned char *) realloc(s, 4+n*(pterm+1)); /* more space */
if (s == 0)
{
printf("Out of memory -- LOGMIN_A, *s\n");
printf("Program terminated - 21\n");
exit(0);
}
memcpy ((s+4+n*pterm), d, n); /* add shrinked CPT to soln array */
pterm++; /* no. of product terms */
cover = 1; /* coverage status */
/***
*** FLAG TERMS COVERED IN THE AD-ARRAY
***/
for (i=0; i<m; i++) /* flag terms just covered */
{
for (j=0; j<count1; j++) /* do for all terms in mt-array */
{
test = memcmp((e+4+nspm*i), (mt+4+nspm*j), nspm);
if (test==0)
{
*(ad+j) = 0; /* flag the adjacency to indicate coverage */
break;
}
}
}
free(e); /* free pointer */
}
free (d); /* free pointer */
}
free(c); /* free pointer */
}
if (count1>0) /* some terms stored for phase II */
{
free(ad); /* free pointers */
free(cp);
free(mt);
free(at);
free(ca);
}
*s = n; /* no. of variables */
*(s+1) = pterm & mask8; /* no. of product terms in 2 bytes */
*(s+2) = pterm>>8 & mask8;
free(temp); /* free pointer */
free(a);
free(b);
return(s); /* return solution array */
}
